package offer.day32;

public class No55Second_isBalanced {
    /*
     * 面试题55：二叉树的深度
     * 题目二：平衡二叉树
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
     * 如果某二叉树中二年以节点的左右子树的深度相差不超过1，
     * 那么它就是一颗平衡二叉树
     *
     * 思路：
     * 方法一：每个节点会遍历多次
     * 在求二叉树深度，对其进行比较保证其左右子树差不超过1
     *优点：简洁
     *缺点：某一个节点会被重复遍历多次，时间效率低
     *
     * 方法二;每个节点遍历一次
     * 可以采用后序遍历  左右根的顺序
     * 遍历每个节点的时候记录其深度，
     * 这样就可以一边遍历，一边判断深度的大小了
     *
     *
     *
     * */
    public static void main(String[] args) {
        No55Second_isBalanced s = new No55Second_isBalanced();
        BinaryTreeNode head = new BinaryTreeNode(5);
        BinaryTreeNode one = new BinaryTreeNode(3);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(2);
        BinaryTreeNode four = new BinaryTreeNode(4);
        BinaryTreeNode five = new BinaryTreeNode(6);
        BinaryTreeNode six = new BinaryTreeNode(8);

        head.left = one;
        head.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = five;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        System.out.println("方法一：");
        if(s.isBalanced_Solution1(head))
            System.out.println("该二叉树是平衡二叉树！");
        else
            System.out.println("该二叉树不是平衡二叉树！！！！");
        
        
        System.out.println("方法二：");
        if(s.isBalanced_Solution2(head))
            System.out.println("该二叉树是平衡二叉树！");
        else
            System.out.println("该二叉树不是平衡二叉树！！！！");
    }

    private boolean isBalanced_Solution2(BinaryTreeNode head) {
        if(head==null) return true;
        int res=treeDepth(head);
        if(res==-1){
            return false;
        }
        return true;
    }

    private int treeDepth(BinaryTreeNode head){
        if(head==null) return 0;
        int left=treeDepth(head.left);
        int right=treeDepth(head.right);
        if(left==-1|| right==-1 || Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;

    }

    private boolean isBalanced_Solution1(BinaryTreeNode head) {
        if(head==null) return true;
        int left=TreeDepth(head.left);
        int right=TreeDepth(head.right);
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced_Solution1(head.left)&&isBalanced_Solution1(head.right);
    }

    private int TreeDepth(BinaryTreeNode head) {
        if(head==null)return 0;
        int left= TreeDepth(head.left);
        int right=TreeDepth(head.right);
        return Math.max(left,right)+1;
    }


}
